package com.algorithm.kmp;

import java.util.Arrays;

/**
 * @author xxy
 * @create 2021 3 25 13:36
 */
public class Kmp {
    public static void main(String[] args) {
        String s1="abababacd";
        String s2="abacd";
        int[] next=next(s2);
        kmpSearch(s1,s2,next);
    }
    public static int kmpSearch(String str1,String str2,int[] next){
        for(int i=0,j=0;i<str1.length();i++){
            while (j>0&&str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }
            if(str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if(j==str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }
    //求部分匹配表
    public static int[] next(String string) {
        int[] next = new int[string.length()];
        next[0]=0;
        for (int i = 1, j = 0; i < string.length(); i++) {
            while (j>0&&string.charAt(i)!=string.charAt(j)){
                j=next[j-1];
            }
            if(string.charAt(i)==string.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}
